1. Field of the Invention
The present invention relates generally to an interleaving/deinterleaving device and method, and in particular, to an interleaving/deinterleaving device and method for a turbo encoder used in radio communication systems such as satellite, ISDN (Integrated Services Digital Network), digital cellular, W-CDMA (Wideband Code Division Multiple Access), IMT-2000 and W-ATM (Wideband Asynchronous Transfer Mode) communication systems.
2. Description of the Related Art
A turbo code is a type of an error correction code which affects the reliability of a digital communication system. An existing turbo coder is divided into a serial turbo coder and a parallel turbo coder. A parallel turbo encoder encodes an input frame of L information bit streams into parity symbols using two simple parallel concatenated codes, wherein recursive systematic convolutional (RSC) encoders are typically used for component encoders. In addition, the parallel turbo encoder includes an interleaver connected between the component encoders.
In the turbo encoder, interleaving is performed to randomize data streams which are input from the component encoders on a frame unit basis and to improve the distance property of a codeword. In particular, it is expected that the turbo encoder will be used in a Supplemental Channel (or traffic channel) of an IMT-2000 (or CDMA-2000) communication system and in a data channel of UMTS (Universal Mobile Telecommunication System) proposed by ETSI (European Telecommunication Standards Institute). Thus, a method for employing an interleaver with a turbo encoder for this purpose is required.
FIG. 1 shows a common parallel turbo encoder, which is disclosed in detail in U.S. Pat. No. 5,446,747, issued on Aug. 29, 1995, which is hereby incorporated by reference.
Referring to FIG. 1, the turbo encoder includes a first component encoder 111 for encoding input frame data, an interleaver 112 for interleaving the input frame data, and a second component encoder 113 for encoding an output of the interleaver 112. A known RSC encoder or NSC (Non-Recursive Systematic Convolutional) encoder is typically used for the first and second component encoders 111 and 113. Such component encoders have different structure according to a coding rate, a constraint length K and a generator polynomial. Further, the interleaver 112 has the same size as the input information bit frame, and rearranges the sequence of the information bits provided to the second component encoder 113 to reduce the correlation between the information bits.
For the internal interleaver (or a turbo interleaver) 112 of the turbo encoder, various interleavers are proposed, such as PN (Pseudo Noise) random interleaver, random interleaver, block interleaver, non-linear interleaver, and S-random interleaver. However, so far, such interleavers are mere algorithms designed to improve their performances in terms of scientific theory rather than practice. When implementing an actual system, the hardware implementation complexity must be taken into consideration. A description will now be made of properties and problems associated with the conventional interleaver for the turbo encoder.
Performance of the turbo encoder is dependent upon the internal interleaver. In general, an increase in the input frame size (i.e., the number of information bits included in one frame) requires an increase in performance of the turbo encoder. However, an increase in interleaver size requires a geometric increase in calculations. Therefore, in general, it is not practical to implement the interleaver for a large frame size.
Generally speaking according to experiments, the random interleaver is superior in performance to the block interleaver. However, the random interleaver is disadvantageous in that an increase in the variety and size of the frame causes an increase in the required memory capacity for storing an interleaver index (i.e., mapping rule or address). That is, the memory capacity required for addressing greatly increases. Therefore, taking the required hardware size into consideration, it is preferable to employ an address enumeration method for reading data stored at a corresponding address by generating an address at every symbol clock using an index generating rule rather than a look-up table method for storing the interleaver index.
In conclusion, when various interleaver sizes are required and the hardware implementation complexity is limited, as in an IMT-2000 or UMTS system, the turbo interleaver should be designed to guarantee optimal interleaver performance by taking inherent limitations into consideration. That is, an interleaver which performs interleaving/deinterleaving according to a specific interleaving rule is required. In addition, the turbo interleaver requires good interleaver properties (e.g., distance property, weight property and random property).
A IMT-2000 or UMTS specification has not yet been given which provides any definition for the turbo interleaver. The forward link and the reverse link defined by the IMT-2000 specification have various types of logical channels and various interleaver sizes. Therefore, in order to meet this variety requirement, an increase in the memory capacity is required. For example, in a CDMA-2000 forward link transmission mode, the interleaver size can vary from 144 bits/frame to 36864 bits/frame.
To sum up, the prior art has the following disadvantages.
First, for the conventional internal interleaver of the turbo encoder, PN random interleavers, random interleavers, block interleavers, non-linear interleavers, and S-random interleavers may be used. However, such interleavers are mere algorithms designed to improve their performances in terms of scientific theory rather than practice. Therefore, when implementing an actual system, the hardware implementation complexity of such interleavers must be considered. However, this is not specifically defined.
Second, since a controller (CPU or host) of the transceiver must store interleaving rules according to the respective interleaver sizes in the existing interleaving method using a look-up table, a host memory requires a separate capacity in addition to an interleaver buffer. That is, when the frame size is varied, and increases in size, an increased memory capacity for storing the interleaver index (i.e., mapping rule or address) is required.
Third, it is not easy to implement an interleaver satisfying both the distance property and the random property.
It is, therefore, an object of the present invention to provide an interleaving/deinterleaving device and method which satisfies distance property, weight property and random property of a turbo encoder in a communication system.
It is another object of the present invention to provide a device and method for performing interleaving using a virtual address area having a size 2mxc3x97Ng determined by adding a specific value to an input data size in a communication system.
It is yet another object of the present invention to provide an interleaving device and method which prevents generation of invalid addresses caused by a specific value added to an input data size to perform interleaving.
It is yet another object of the present invention to provide a method for determining an optimal initial value of a PN sequence generator which generates a random address component according to an address area of an internal interleaver in a turbo encoder.
To achieve the above object, there is provided a device for generating L addresses, which are smaller in number than 2mxc3x97Ng virtual addresses, for reading data from an interleaver memory in which L data bits are stored. The device comprises a selection circuit including Ng PN (Pseudo Noise) generators each including m memories, wherein one of the PN generators generates (OSV-1) offset values (OSV) satisfying OSV=2mxc3x97Ngxe2x88x92L and (2mxe2x88x92OSV) non-zero states in response to a first clock signal and the other PN generators each generate (2mxe2x88x921) non-zero states, wherein the selection circuit selects the PN generators according to a predetermined order in response to a select signal and outputs a state generated from the selected PN generator; means for detecting each offset state from one PN generator, providing said select signal for not selecting said one PN generator so that the detected offset state is not output, and generating high address bits related to each selection of the PN generators in response to clock pulses of a second clock signal having a shorter period than the first clock signal; means for generating low address bits determined by subtracting one from each state output from the selection circuit when a number of selection periods of the PN generators is smaller than 2m, and generating low address bits corresponding to 2mxe2x88x921 when the number of selection periods is 2m; and an address buffer for storing the addresses, said L addresses each being comprised of the high address bits and the low address bits.